package 简单算法;

/**
 * Copyright: Copyright (c) 2019 Hu-Cheng
 *
 * @ClassName: 数组排序.java
 * @Description: 数据的所有排序方法
 *
 * @version: v1.0.0
 * @author: hucheng
 * @date: Oct 17, 2019 11:02:09 AM
 *
 */
public class 数组排序 {

	public static void main(String[] args) {
//		bubbleSort();
//		fastSort();
//		selectSort();
//		insertSort();
		shellSort();
	}
	
	/**
	 * 希尔排序的原理：根据需求，如果你想要结果从大到小排序，它首先会将数组进行分组，然后将较大的值移到前面，教小值移到后面
	 * 最后将整个数组进行进入排序，这样比起一开始就用插入排序减小了数据交换和移动的次数，可以说希尔排序是加强版的插入排序
	 * 那数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
	 * 5、2、8和9、1、3、4第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小于increment的数组值相比较
	 * 此例子是按照从大到小排序，所以较大的值会在前面，第一次排序后为9,2,8,5,1,3,4;
	 * 第一次后increment的值变为3/2=1,此时对数组进行插入排序
	 * 实现数组从大到小排
	 */
	public static void shellSort() {
		int[] a = {8,11,5,22,18,5,6,36};
		
		//18,11,6,36,8,5,5,22
		
		sortbefore(a);
		
		int size = a.length;
		int j = 0;
		int temp = 0;
		for (int increment = size/2; increment > 0; increment/=2) {
			for (int i = increment; i < size; i++) {
				temp = a[i];
				for (j = i; j>=increment ; j-=increment) {
					if(temp > a[j - increment]) {
						a[j] = a[j-increment];
					}else {
						break;
					}
				}
				a[j] = temp;
			}
		}
		sortafter(a);
	}
	
	

	/**
	 * 插入排序 
	 * 1.从第一个元素开始，该元素可以认为已经被排序的 
	 * 2.取出下一个元素，在已经排好序的元素中从后向前扫描
	 * 3.如果该元素(已排序)大于新元素,将该元素移到下一个位置 
	 * 4.重复步骤3，知道找到已排序的元素小于或等于新元素的位置 
	 * 5.将新元素插入到该位置中
	 * 6.重复步骤2~5
	 */
	public static void insertSort() {
		int[] a = { 8, 11, 5, 22, 18, 5, 6, 36 };
		sortbefore(a);
		int j = 0,temp = 0;
		for (int i = 0; i < a.length; i++) {
			temp = a[i];
			
			for (j = i; j>0 && temp < a[j-1]; j--) {
				a[j] = a[j-1];
			}
			a[j] = temp;
		}
		
//		for (j = i; j > 0 ; j--) {
//			if(temp < a[j - 1]) {
//				int k = a[j];
//				a[j] = a[j-1];
//				a[j - 1] = k;
//			}
//		}
		
		
		sortafter(a);

	}

	/**
	 * 选择排序算法 每次循环现在先找到最小的元素 然后将最小的元素方给到序列首位 下次循环就从第二位开始找，每次循环首位都是已经排序好的
	 * 
	 */
	public static void selectSort() {
		int[] a = { 8, 11, 5, 22, 18, 5, 6, 36 };

		System.out.print("排序前：");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}

		int length = a.length;
		for (int i = 0; i < a.length; i++) {
			// 假设最小的元素下标是i
			int min = i;
			// 再将min与序列中的所有元素相比，取出最小的值
			// 每次排序，i前面的数值都是排好的，所以不用再排序，所以就从j = i开始比较
			for (int j = i; j < length; j++) {
				if (a[j] <= a[min]) {
					min = j;
				}
			}
			// 当前循环首位跟最小的一位交换位置，当前首位就是i
			int temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}

		System.out.println();

		System.out.print("排序后：");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}

	}

	/**
	 * 快速排序 定义两个变量low high low从左向右开始，high从右向左开始 high>基准数 high--，就向左移动一位
	 * 
	 * 直到 low<high && high>=基准数 不成立 ，就将当前high值给low low = high
	 *
	 * 然后进行 low<基准数 low++，就向右移动一位 直到 low<high && low <= 基准数 不成立，就将当前low值给high high =
	 * low
	 * 
	 * 循环到 low == high 的时候，将基准数值给low 返回low下标，中间轴的位置就找好了 然后这时候数组就以low中间轴的位置，被分割成两部分
	 * 分别对这两部分一个从左，一个从右进行排序即可
	 */
	public static void fastSort() {
		int[] a = { 8, 11, 5, 22, 18, 5, 6, 36 };
		System.out.print("排序前：");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}

		quickSort(a, 0, a.length - 1);

		System.out.println();
		System.out.print("排序后：");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}

	}

	public static void quickSort(int[] a, int low, int high) {
		if (low < high) {
			// 将数据一分为二,一部分向左边排序，一部分向右边排序
			int middle = getMiddle(a, low, high);
			// 对低字段进行递归排序
			quickSort(a, low, middle - 1);
			// 对高字段进行递归排序
			quickSort(a, middle + 1, high);
		}
	}

	public static int getMiddle(int[] a, int low, int high) {
		int temp = a[low];
		while (low < high) {
			while (low < high && a[high] >= temp) {
				high--;
			}
			a[low] = a[high];

			while (low < high && a[low] <= temp) {
				low++;
			}
			// 比中轴大的记录移到高端
			a[high] = a[low];
		}
		// 中轴记录到尾
		a[low] = temp;
		return low;
	}

	/**
	 * 冒泡排序 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
	 * 在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。
	 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
	 */
	public static void bubbleSort() {
		int[] a = { 10, 5, 6, 7, 3, 2, 98, 13 };
		System.out.print("排序前: ");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}
		System.out.println();

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length - 1; j++) {
				if (a[j] > a[j + 1]) {
					int temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}

		System.out.print("升序后: ");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}

		System.out.println();
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length - 1; j++) {
				if (a[j] < a[j + 1]) {
					int temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}
		}

		System.out.print("降序后: ");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}
	}

	public static void sortbefore(int[] a) {
		System.out.print("排序前：");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}
		System.out.println();
	}

	public static void sortafter(int[] a) {
		System.out.print("排序后：");
		for (int i = 0; i < a.length; i++) {
			if (i == a.length - 1) {
				System.out.print(a[i]);
			} else {
				System.out.print(a[i] + ",");
			}
		}
		System.out.println();
	}

}
